package DataStructures.Sort;

/**
 * Created by 其 on 2016/4/19.
 */
public class QuickSort {
    public QuickSort(int[] a){
        quick(a);
    }
    private int getMiddle(int[] list, int low, int high) {
        int temp = list[low];    //数组的第一个作为中轴
        while (low < high){
            while (low<high && list[high]>=temp) {
                high--;
            }
            list[low] =list[high];   //比中轴小的记录移到低端
            while (low <high && list[low]<=temp) {
                low++;
            }
            list[high] = list[low];   //比中轴大的记录移到高端
        }
        list[low] = temp;              //中轴记录到尾
        return low;                   //返回中轴的位置
    }
    private void quickSort(int[] list, int low, int high) {
        if (low < high){
            int middle = getMiddle(list, low, high);  //将list数组进行一分为二
            quickSort(list, low, middle - 1);       //对低字表进行递归排序
            quickSort(list, middle + 1, high);       //对高字表进行递归排序
        }
    }
    private void quick(int[] a2) {
        if (a2.length > 0) {    //查看数组是否为空
            quickSort(a2,0, a2.length - 1);
        }
    }
}
